<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body></body>
  <script>
    function arrayToTree(arr) {
      // 创建一个 Map 对象用于存储节点，Map 具有缓存特性，可以快速通过 key 查找 value
      const idMap = new Map()
      // 创建结果数组，用于存储根节点
      const result = []

      // 第一次遍历：初始化 Map，为每个节点创建对象并添加 children 数组
      arr.forEach((item) => {
        // 将每个节点的 id 作为 key，节点对象（包含 children 数组）作为 value 存入 Map
        // 使用扩展运算符 ...item 复制原对象的所有属性，并添加空的 children 数组
        idMap.set(item.id, { ...item, children: [] })
      })

      // 第二次遍历：构建树形结构，建立父子关系
      arr.forEach((item) => {
        // 从 Map 中根据 parentId 获取父节点对象，Map 的 get 方法时间复杂度为 O(1)

        console.log(idMap,'idMap11111');
        
        const parent = idMap.get(item.parentId) 
        if (parent) {
          // 如果找到父节点，将当前节点添加到父节点的 children 数组中
          // 这里 idMap.get(item.id) 获取的是已经创建好的节点对象（带有 children 数组）
          parent.children.push(idMap.get(item.id))
        } else {
          // 如果没有父节点（parentId 为 null 或找不到对应父节点），说明是根节点
          // 将根节点添加到结果数组中
          result.push(idMap.get(item.id))
        }
      })
      console.log(result,'result');
      
      // 返回构建好的树形结构
      return result
    }

    // 测试数据：包含 id、name 和 parentId 的扁平数组
    const arr = [
      { id: 1, name: "Node 1", parentId: null },   // 根节点
      { id: 2, name: "Node 2", parentId: 1 },      // Node 1 的子节点
      { id: 3, name: "Node 3", parentId: 1 },      // Node 1 的子节点
      { id: 4, name: "Node 4", parentId: 2 },      // Node 2 的子节点
      { id: 5, name: "Node 5", parentId: 2 },      // Node 2 的子节点
      { id: 6, name: "Node 6", parentId: 3 },      // Node 3 的子节点
      { id: 7, name: "Node 7", parentId: 3 },      // Node 3 的子节点
      { id: 8, name: "Node 8", parentId: 4 },      // Node 4 的子节点
      { id: 9, name: "Node 9", parentId: 4 },      // Node 4 的子节点
      { id: 10, name: "Node 10", parentId: 5 },    // Node 5 的子节点
    ]

    // 调用函数并以 JSON 格式输出结果，便于查看树形结构
    console.log(JSON.stringify(arrayToTree(arr), null, 2))
  </script>
</html>
